#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define NORMAL 0
#define THRENA 1 
// 前序

//这里左儿子记录前驱，右儿子记录后继
typedef struct Node {
    int val, ltag, rtag;//val结点的值，ltag记录是否有前驱,rtag记录是否有后继
    struct Node *lchild, *rchild;
} Node;
 
Node *getNewNode(int val) {//获取新的结点
    Node *root = (Node *)malloc(sizeof(Node));
    root->lchild = root->rchild = NULL;
    root->rtag = root->ltag = NORMAL;//NORMAL表示还未有前驱或后继
    root->val = val;
    return root;
}
 
Node *insert(Node *root, int val) {//添加结点，组成普通的二叉树
    if (!root) return getNewNode(val);
    if (root->val == val) return root;
    if (root->val > val) root->lchild = insert(root->lchild, val);
    else root->rchild = insert(root->rchild, val);
    return root;
}
 
void build_Thread(Node *root) {//建立线索化
    if (!root) return ; 
    static Node *pre = NULL;//使用静态变量使得pre值不随程序递归而改变
    Node *left = root->lchild;//记录当前结点左右儿子 
    Node *right = root->rchild;
    if (root->ltag == NORMAL) {//当前结点没有前驱结点
        root->lchild = pre;//给当前结点赋值前驱结点
        root->ltag = THRENA;//标记有前驱结点
    }
    if (pre && pre->rtag == NORMAL) {//如果它的前驱结点没有后继，并且前驱结点不为NULL
        pre->rchild = root;//将前驱结点的后继附上当前结点
        pre->rtag = THRENA;//标记前驱结点有后继了
    }
    pre = root;//pre等于当前递归的结点
    build_Thread(left);//递归左子树
    build_Thread(right);//在递归右子树
    return ;
}
 
void output(Node *root) {//遍历线索化二叉树
    if (!root) return ;
    Node *p = root;
    while (p) {
        printf("%d ", p->val);
        if (p->rtag == THRENA) p = p->rchild;//说明当前结点有后继直接往右节点也就是后继结点继续遍历
        else if (p->rtag == NORMAL) break;//如果当前结点没有后继结束遍历 
    }
    return ;
}
 
 
void preface(Node *root) {//普通前序递归遍历
    if (!root) return ;
    printf("%d ", root->val);
    if (root->ltag == NORMAL) preface(root->lchild);
    if (root->rtag == NORMAL) preface(root->rchild);
    return ;
}
 
void clearNode(Node *root) {//回收空间
    if (!root) return ;
    if (root->ltag == NORMAL) clearNode(root->lchild);
    if (root->rtag == NORMAL) clearNode(root->rchild);
    free(root);
    return ;
}
 
 
int main() {
    srand(time(0));//获取当期计算时间，获取随机数
    Node *root = NULL;
    for (int i = 0; i < 10; i++) {
        int val = rand() % 100;
        root = insert(root, val);
    }
    preface(root);//先打印普通前序遍历
    putchar(10);//换行
    build_Thread(root);//建立线索化
    output(root);//输出前序线索化
    putchar(10);
    clearNode(root);
    return 0;
}
